import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists {

    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode temp = ans;
        while (true) {
            int arrMin = getArrMin(lists);
            if (arrMin == Integer.MAX_VALUE) break;
            temp.next = new ListNode(arrMin);
            temp = temp.next;
        }
        return ans.next;
    }

    public int getArrMin(ListNode[] index) {
        int min = Integer.MAX_VALUE;
        int temp = 0;
        for (int i = 0; i < index.length; i++) {
            if (index[i] != null && index[i].val <= min) {
                temp = i;
                min = index[i].val;
            }
        }
        if (min == Integer.MAX_VALUE) return Integer.MAX_VALUE;
        index[temp] = index[temp].next;
        return min;
    }

    public ListNode merge(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) return node1 == null ? node2 : node1;
        ListNode head = new ListNode();
        ListNode temp = head;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                temp.next = node1;
                node1 = node1.next;
            } else {
                temp.next = node2;
                node2 = node2.next;
            }
            temp = temp.next;
        }
        temp.next = node1 == null ? node2 : node1;
        return head.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) return new ListNode();
        ListNode ans = null;
        for (int i = 0; i < lists.length; i++) {
            ans = merge(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                listNodes.offer(lists[i]);
            }
        }
        ListNode head = new ListNode();
        ListNode temp = head;
        while (!listNodes.isEmpty()) {
            ListNode poll = listNodes.poll();
            temp.next = poll;
            temp = temp.next;
            if (poll.next != null) {
                listNodes.offer(poll.next);
            }
        }
        return head.next;
    }
}
